package tree;

/**
 * @author : Rookie
 * @description : 二叉树的最近公共祖先
 * @date : 2023/10/29
 */
public class NearestCommonAncestor {

    public static void main(String[] args) {
        int[] tree = new int[] {3,5,1,6,2,0,8,-1,-1,7,4,-1,-1,-1,-1};
        TreeNode root = BinaryTreeUtil.buildTree(tree);
        TreeNode treeNode = getNearestCommonAncestor(root, 5, 2);
        System.out.println(treeNode);
    }

    public static TreeNode getNearestCommonAncestor(TreeNode node,int p,int q) {
        if (node == null || node.element == p || node.element == q) {
            return node;
        }
        // 左
        TreeNode left = getNearestCommonAncestor(node.left, p, q);
        // 右
        TreeNode right = getNearestCommonAncestor(node.right, p, q);
        // 根
        // 左子树和右子树返回均不为空，则当前节点就是最近公共祖先
        if (left != null && right != null) {
            return node;
        }
        // 处理左右子树有1个为空的情况
        if (left != null && right == null) {
            return left;
        } else if (left == null && right != null) {
            return right;
        } else {
            return null;
        }
    }
}
